O(log N)
入力のサイズが2倍になっても、計算時間が定数だけ増えることを意味する
logが出現する理由
sort済みの配列から特定の値を探すとき、毎回配列を半分に分割して検索する
例えば、サイズ $ n = 16 の配列があるとする
最悪でも何回の比較で終わるか考える
1回目: 16個 → 半分に分割（8個）
2回目: 8個 → 半分に分割（4個）
3回目: 4個 → 半分に分割（2個）
4回目: 2個 → 半分に分割（1個）
5回目: 1個（発見 or 失敗）
つまり、何回分割すれば1になるか？を考えれば良い
これは、$ x 回の操作で $ n が 1 になるという式
$ \frac{n}{2^x} = 1を解くことで求まる
両辺の対数を取ると
$ x = \log_2 nになる
例